\begin{aosachapter}{SnowFlock}{s:snowflock}{Roy Bryant and Andr\'e{s} Lagar-Cavilla}
%% Based on EN-Revision r272

%% Cloud computing provides an attractively affordable computing
%% platform.  Instead of buying and configuring a physical server, with
%% all the associated time, effort and up front costs, users can rent
%% ``servers'' in the cloud with a few mouse clicks for
%% less than 10 cents per hour. Cloud providers keep their costs low by
%% providing virtual machines (VMs) instead of physical computers. The
%% key enabler is the virtualization software, called a virtual machine
%% monitor (VMM), that emulates a physical machine. Users are safely
%% isolated in their ``guest'' VMs, and are blissfully unaware that they
%% typically share the physical machine (``host'') with many others.
クラウドコンピューティングは、お手頃な価格で魅力的な計算プラットフォームを提供してくれる。
物理的なサーバーを購入して設定するのには時間や手間もかかるし、初期費用も必要だ。
クラウドコンピューティングなら、クラウドにある「サーバー」を簡単にレンタルできる。
マウスを何度かクリックするだけだし、一時間あたりのコストは10セントに満たない。
クラウド事業者がこんなに安価でサーバーを提供できている理由は、
物理的なコンピューターではなく仮想マシン(VM)を使っているからだ。
それを実現する肝となるのが仮想化ソフトウェアで、これは仮想マシンモニター(VMM)
と呼ばれている。物理的なマシンをエミュレートする仕組みだ。
各ユーザーはそれぞれ安全に隔離された「ゲスト」VMを利用する。
ふつうは複数のゲストが一台の物理マシン(「ホスト」)を共有しているのだが、
ありがたいことにユーザーはそれを気にせずに済む。

%% \begin{aosasect1}{Introducing SnowFlock}
\begin{aosasect1}{SnowFlockのご紹介}

%% Clouds are a boon to agile organizations. With physical servers, users
%% are relegated to waiting impatiently while others (slowly) approve the
%% server purchase, place the order, ship the server, and install and
%% configure the Operating System (OS) and application stacks. Instead of
%% waiting weeks for others to deliver, the cloud user retains control of
%% the process and can create a new, standalone server in minutes.
クラウドは、アジャイルな組織にとってはとてもありがたいものである。
物理サーバーの場合を考えてみよう。
まずサーバー購入の稟議書を書いて承認を得て(これ、時間がかかるよね)、
それから発注。そして、サーバーが発送されてきたら
OSやアプリケーションをインストールして設定をする。
その間、実際のユーザーはずっと待ち続けることになる。
クラウドを使えば、実際に使えるようになるまで何週間も待たされることもない。
新しいスタンドアロンのサーバーを、ほんの数分あれば自分の手で作れるのだ。

%% Unfortunately, few cloud servers stand alone.  Driven by the quick
%% instantiation and pay-per-use model, cloud servers are typically
%% members of a variable pool of similarly configured servers performing
%% dynamic and scalable tasks related to parallel computing, data mining,
%% or serving web pages.  Because they repeatedly boot new instances from
%% the same, static template, commercial clouds fail to fully deliver on
%% the promise of true on-demand computation. After instantiating the
%% server, the cloud user must still manage cluster membership and broker
%% the addition of new servers.
残念ながら、それ単体でやっていけるクラウドサーバーはほとんどない。
お手軽インストールの従量課金モデルということもあって、
クラウドサーバーは一般的に、
同じように設定されたサーバー群の一員となることが多い。
これらを使って、並列コンピューティングやデータマイグレーション
そしてウェブページの提供などの動的かつスケーラブルな作業をこなすことになる。
同じ静的テンプレートから新たなインスタンスを繰り返し起動することになるので、
商用クラウドサービスでは真のオンデマンド利用を保証することができない。
いったんサーバーのインスタンスを作ったら、クラスタのメンバー管理をしたり
ブローカーに新たなサーバーを追加したりといった作業が必要となる。

%% SnowFlock addresses these issues with VM Cloning, our proposed cloud
%% API call. In the same way that application code routinely invokes OS
%% services through a syscall interface, it could now also invoke cloud
%% services through a similar interface. With SnowFlock's VM Cloning,
%% resource allocation, cluster management, and application logic can be
%% interwoven programmatically and dealt with as a single logical
%% operation.
SnowFlockは、これらの問題に対応するためにVM Cloningを利用する。
このときに使うのは、私たちが提案するクラウドAPIだ。
アプリケーションのコードがごく普通にシステムコールを使って
OSのサービスを起動するのと同じく、
SnowFlockも同様のインターフェイスでクラウドサービスを起動できるようになったのだ。
SnowFlockのVM Cloningやリソース割り当て、クラスタ管理、
アプリケーションのロジックなどをプログラムで取りまとめられるようになり、
単一の論理操作として扱えるようになった。

%% The VM Cloning call instantiates multiple cloud servers that are
%% identical copies of the originating parent VM up to the point of
%% cloning. Logically, clones inherit all the state of their parent,
%% including OS- and application-level caches. Further, clones are
%% automatically added to an internal private network, thus effectively
%% joining a dynamically scalable cluster. New computation resources,
%% encapsulated as identical VMs, can be created on-the-fly and can be
%% dynamically leveraged as needed.
VM Cloningをコールすると、クローニングの時点での親VMとまったく同じ内容で
複数のクラウドサーバーのインスタンスを作成する。
論理的に、これらのクローンは親のすべての状態を引き継ぐ。OSレベルだけでなく
アプリケーションレベルのキャッシュも含めてである。さらに、
クローンが自動的に内部のプライベートネットワークに追加されるので、
動的でスケーラブルなクラスタにうまく参加できるようになる。
個別のVMにまとめた新たな計算機リソースをその場で作れ、
必要に応じて動的に活用できる。

%% To be of practical use, VM cloning has to be applicable, efficient,
%% and fast. In this chapter we will describe how SnowFlock's
%% implementation of VM Cloning can be effectively interwoven in several
%% different programming models and frameworks, how it can be implemented
%% to keep application runtime and provider overhead to a minimum, and
%% how it can be used to create dozens of new VMs in five seconds or
%% less.
現実的に使えるレベルにするには、ただVMのクローンができるだけではなく、
十分に効率的かつ高速でなければならない。本章ではSnowFlockにおける
VM Cloningの実装を取り上げる。
さまざまなプログラミングモデルやフレームワークをひとつにまとめ、
アプリケーションのランタイムやプロバイダーのオーバーヘッドを最小限に抑え、
何十もの新たなVMを5秒とかからずに作れるようにした、その方法を説明する。

%% With an API for the programmatic control of VM Cloning with bindings
%% in C, C++, Python and Java, SnowFlock is extremely flexible and
%% versatile.  We've successfully used SnowFlock in prototype
%% implementations of several, quite different, systems.  In parallel
%% computation scenarios, we've achieved excellent results by explicitly
%% cloning worker VMs that cooperatively distribute the load across many
%% physical hosts. For parallel applications that use the Message Passing
%% Interface (MPI) and typically run on a cluster of dedicated servers,
%% we modified the MPI startup manager to provide unmodified applications
%% with good performance and much less overhead by provisioning a fresh
%% cluster of clones on demand for each run. Finally, in a quite
%% different use case, we used SnowFlock to improve the efficiency and
%% performance of elastic servers.  Today's cloud-based elastic servers
%% boot new, cold workers as needed to service spikes in demand. By
%% cloning a running VM instead, SnowFlock brings new workers on line 20
%% times faster, and because clones inherit the warm buffers of their
%% parent, they reach their peak performance sooner.
VM Cloningをプログラムで制御するためのAPIを提供しており、
CやC++、PythonそしてJavaのバインディングも用意されている。
そのおかげで、SnowFlockは極めて柔軟で幅広く使えるものになっている。
私たちはこれまでに、SnowFlockをつかってさまざまなシステムのプロトタイプ実装を成功させてきた。
並列処理を要する場面では、多数の物理ホストに対する負荷分散を考慮して
ワーカーVMのクローン先を明示的に選ぶようにして、すばらしい結果を達成した。
Message Passing Interface (MPI)を扱う並列アプリケーションで、
専用サーバーのクラスタ環境で実行されることが多いというものがあった。
このときは、MPIスタートアップマネージャーに手を加えることで、
アプリケーション側を一切変更せずによりよいパフォーマンスと
より低いオーバーヘッドを実現した。クローンによる未使用のクラスタを、
実行時にオンデマンドで配布できるようにしたのだ。
最後にもうひとつ紹介しよう。今までの例とはかなり違う使い方だが、
SnowFlockを使って、伸縮自在なサーバー群(elastic servers)の効率とパフォーマンスを改善したのだ。
いまどきのクラウドベースの伸縮自在なサーバー群は、
サービスの利用量が急増した場合に必要に応じて新たなワーカーを起動するようになっている。
そうではなく、稼働中のVMをクローンすることで、SnowFlockは
新たなワーカーの立ち上げを20倍も高速化した。
また、クローンは稼働中の親サーバーのバッファーも引き継ぐので、
まっさらなサーバーを立ち上げるのに比べてより高速にフル稼働状態に持ち込める。

\end{aosasect1}

%% \begin{aosasect1}{VM Cloning}
\begin{aosasect1}{VMのクローニング}

%% As the name suggests, VM clones are (nearly) identical to their parent
%% VM\@. There are actually some minor but necessary differences to avoid
%% issues such as MAC address collisions, but we'll come back to that
%% later. To create a clone, the entire local disk and memory state must
%% be made available, which brings us to the first major design tradeoff:
%% should we copy that state up-front or on demand?
その名が示す通り、VMのクローンは親VMとほぼ同じものである。
ただ、実際には必要最小限の相違点がある。MACアドレスの衝突みたいな問題を回避するためだ。
それについては後で説明する。
クローンを作るということは、ローカルディスク全体とメモリの状態をコピーして使えるようにするということだ。
ここで、設計上の最初のトレードオフに直面する。
状態のコピーは事前に行うべきだろうか。それともその場でオンデマンドで行うべきだろうか。

%% The simplest way to achieve VM cloning is to adapt the standard VM
%% ``migration'' capability.  Typically, migration is used when a running
%% VM needs to be moved to a different host, such as when the host
%% becomes overloaded or must be brought down for maintenance. Because
%% the VM is purely software, it can be encapsulated in a data file that
%% can then be copied to a new, more appropriate host, where it picks up
%% execution after a brief interruption. To accomplish this,
%% off-the-shelf VMMs create a file containing a ``checkpoint'' of the VM,
%% including its local filesystem, memory image, virtual CPU (VCPU)
%% registers, etc. In migration, the newly booted copy replaces the
%% original, but the process can be altered to produce a clone while
%% leaving the original running. In this ``eager'' process, the entire VM
%% state is transferred up front, which provides the best initial
%% performance, because the entire state of the VM is in place when
%% execution begins.  The disadvantage of eager replication is that the
%% laborious process of copying the entire VM must happen before
%% execution can begin, which significantly slows instantiation.
VMクローニングを実現するためのいちばんシンプルな方法は、
標準的な「マイグレーション」機能を使うことだ。
マイグレーションの使いどころとして一般的なのは、稼働中のVMを別のホストへの移動だ。
今のホストでは負荷に耐えられなくなっただとか、今のホストのメンテナンスで
電源断が発生するなどという場合に利用する。
VMは純粋にソフトウェアなので、ひとつのデータファイルにまとめることができる。
そのファイルを新しいホストにコピーして、少し手を加えた後で起動することになる。
これを実現するために、既製のVMMはVMの「チェックポイント」を含めたファイルを作る。
ローカルファイルシステムの状態やメモリのイメージ、仮想CPU(VCPU)のレジスタの状態なども
含めたファイルである。マイグレーションのときは、
元のVMのかわりに新たなコピーを起動する。ただ、起動プロセスの途中で
クローンを作る処理に入り、元のVMは稼働したままにしておく。
この「貪欲な」手順では、VM全体の状態を事前に転送する。そうすることで、
初期パフォーマンスを最大化している。というのも、
VM全体の状態が実行開始時にそろっているからだ。
この方式のレプリケーションの弱点は、VM全体のコピーという
手間のかかる作業をしてからでないと実行開始できないということ。
つまり、インスタンスを作るのにとても時間がかかるということだ。

%% The other extreme, adopted by SnowFlock, is ``lazy'' state
%% replication.  Instead of copying everything the VM might ever need,
%% SnowFlock transfers only the vital bits needed to begin execution, and
%% transfers state later, only when the clone needs it. This has two
%% advantages.  First, it minimizes the instantiation latency by doing as
%% little work as possible up front. Second, it increases the efficiency
%% by copying only the state that is actually used by the clone. The
%% yield of this benefit, of course, depends on the clone's behavior, but
%% few applications access every page of memory and every file in the
%% local filesystem.
SnowFlockが採用したのは、それとは正反対の「怠惰な」手順による状態のレプリケーションだ。
VMが必要とするであろうすべての内容をコピーするのではなく、
SnowFlockは起動するために最低限必要なものだけをとりあえず転送する。
その他の部分については、クローン側で必要となったときになってはじめて転送する。
この方式には二つの利点がある。
まず、起動にかかる時間が最短になるということ。事前に必要な処理が限られているからである。
次に、効率がよくなるということ。クローンが実際に使う状態だけをコピーするからである。
後者の利点が得られるかどうかは、もちろんクローンの状態に依存する。
しかし、メモリの全ページにアクセスしたりローカルファイルシステム上の
全ファイルにアクセスしたりするようなアプリケーションなどほとんど存在しない。

%% However, the benefits of lazy replication aren't free. Because the
%% state transfer is postponed until the last moment, the clone is left
%% waiting for state to arrive before it can continue execution. This
%% This situation parallels swapping of memory to disk in time-shared workstation:
%% applications are blocked waiting for state to be fetched from a high latency source.
%% In the case of SnowFlock, the
%% blocking somewhat degrades the clone's performance; the severity of
%% the slowdown depends on the application.  For high performance
%% computing applications we've found this degradation has little impact,
%% but a cloned database server may perform poorly at first. It should be
%% noted that this is a transient effect: within a few minutes, most of
%% the necessary state has been transferred and the clone's performance
%% matches that of the parent.
とはいえ、怠惰なレプリケーションが万能なわけではなく、それなりの代償を払うことになる。
状態の転送を最後の最後まで先送りにするので、実行し続けるためには転送が完了するまで待たなければいけない。
この状況は、時分割方式のワークステーションでメモリをディスクにスワップさせるときに似ている。
レイテンシーの高いところから状態を取得してくるまでアプリケーションの処理がブロックされてしまうのだ。
SnowFlockの場合、このブロックによってクローンのパフォーマンスが多少落ちる。
このスローダウンがどの程度の影響を及ぼすかは、アプリケーションによって異なる。
高性能計算アプリケーションに関しては、この問題の影響はほとんどないことが経験上わかっている。
しかし、データベースサーバーをクローンした場合などは出だしのパフォーマンスが
不十分になるだろう。注意すべきなのは、これはあくまでも一時的な問題だということだ。
数分もすれば必要な状態の大半は転送し終えるので、
クローンのパフォーマンスは親と同じ程度になる。

%% As an aside, if you're well versed in VMs, you're likely wondering if
%% the optimizations used by ``live'' migration are useful here. Live
%% migration is optimized to shorten the interval between the original
%% VM's suspension and the resumption of execution by the new copy.  To
%% accomplish this, the Virtual Machine Monitor (VMM) pre-copies the VM's state while the original
%% is still running, so that after suspending it, only the recently
%% changed pages need to be transferred. This technique does not affect
%% the interval between the migration request and the time the copy
%% begins execution, and so would not reduce the instantiation latency of
%% eager VM cloning.
余談だが、VMに詳しい人ならこう思うかもしれない。
「そんなときって、ライブマイグレーションの最適化機能が使えるんじゃないの？」
ライブマイグレーションの最適化とは、元のVMを停止してから新たなコピーを
起動するまでのインターバルを短縮することである。
これを実現するには、元のVMが動いている間に
Virtual Machine Monitor (VMM)がVMの状態をコピーすればよい。
これで、元のVMを停止したときには直近で変更があったページだけを転送すればいいことになる。
ただ、このテクニックを使ったところで、マイグレーションのリクエストから
コピーが立ち上がるまでの所要時間は変わらない。そのため、
貪欲なVMクローニングにおけるインスタンス作成時間の短縮には役立たない。

\end{aosasect1}

%% \begin{aosasect1}{SnowFlock's Approach}
\begin{aosasect1}{SnowFlockの手法}

%% SnowFlock implements VM cloning with a primitive called ``VM Fork'',
%% which is like a standard Unix \code{fork}, but with a few
%% important differences.  First, rather than duplicating a single
%% process, VM Fork duplicates an entire VM, including all of memory, all
%% processes and virtual devices, and the local filesystem.  Second,
%% instead of producing a single copy running on the same physical host,
%% VM Fork can simultaneously spawn many copies in parallel. Finally, VMs
%% can be forked to distinct physical servers, letting you quickly
%% increase your cloud footprint as needed.
SnowFlockは、VMのクローニングを「VMフォーク」というプリミティブで実装している。
これは標準的なUnixの\code{fork}と似ているが、重要な違いがいくつかある。
まず、Unixの\code{fork}は単一のプロセスを複製するが、VMフォークの場合はVM全体を複製する。
メモリやプロセスや仮想デバイス、そしてローカルファイルシステムの状態も含めて複製するのだ。
次に、Unixの\code{fork}は同じ物理ホスト上にコピーをひとつ作るだけだが、
VMフォークの場合は複数のコピーを並列で作成できる。
最後に、VMフォークは別のサーバー上に作ることもできる。
これを利用すれば、クラウド上でのフットプリントを必要に応じて拡大できる。

%% The following concepts are key to SnowFlock:
SnowFlockの鍵となるのが、これらの概念だ。

\begin{aosaitemize}

  %% \item Virtualization: The VM encapsulates the computation
  %% environment, making clouds and machine cloning possible.
  \item 仮想化：VMが計算環境をカプセル化することで、クラウドを作ったりマシンをクローンしたりできるようにする。

  %% \item Lazy Propagation: The VM state isn't copied until it's needed,
  %% so clones come alive in a few seconds.
  \item 緩やかな伝搬：VMの状態は、必要になるまでコピーしない。そうすることで、クローンを数秒で立ち上げられるようにする。

  %% \item Multicast: Clone siblings have similar needs in terms of VM
  %% state. With multicast, dozens of clones start running as quickly
  %% as one.
  \item マルチキャスト：クローンした兄弟たちは、VMの状態が同じになっていなければいけない。
  マルチキャストを使えば、何十ものクローンをすばやく稼働させることができる。

  %% \item Page Faults: When a clone tries to use missing memory, it
  %% faults and triggers a request to the parent. The clone's execution
  %% is blocked until the needed page arrives.
  \item ページフォルト：まだクローン側に存在しないメモリを使おうとしたときは、
  処理を止めて親にリクエストをしなければならない。クローンの実行は、必要なページが届くまでブロックする。

  %% \item Copy on Write (CoW): By taking a copy of its memory and disk
  %% pages before overwriting them, the parent VM can continue to run
  %% while preserving a frozen copy of its state for use by the clones.
  \item コピーオンライト (CoW)：メモリやディスクスペースのコピーを取ってから上書きする。
  これで、親VMが処理を続けつつ、それ以前の状態のコピーをクローンが使えるようになる。

\end{aosaitemize}

%% We've implemented SnowFlock using the Xen virtualization system, so
%% it's useful to introduce some Xen-specific terminology for clarity. In
%% a Xen environment, the VMM is called the hypervisor, and VMs are
%% called domains. On each physical machine (host), there is a privileged
%% domain, called ``domain 0'' (dom0), that has full access to the host
%% and its physical devices, and can be used to control additional guest, or ``user'',
%% VMs that are called ``domain U'' (domU).
SnowFlockの実装にはXenを利用した。ここで、Xen特有の用語を念のために紹介しておこう。
Xenの環境ではVMMのことをハイパーバイザと呼び、一方VMのことをドメインと呼ぶ。
物理マシン(ホスト)ごとに特権ドメイン``domain 0'' (dom0)があり、これはホストとその物理デバイスに対する
完全なアクセス権を持つ。また、この特権ドメインを使ってゲスト(あるいは``user'')VMを作ることができる。
このドメインのことを``domain U'' (domU)と呼ぶ。

%% In broad strokes, SnowFlock consists of a set of modifications to the
%% Xen hypervisor that enable it to smoothly recover when missing
%% resources are accessed, and a set of supporting processes and systems
%% that run in dom0 and cooperatively transfer the missing VM state, and
%% some optional modifications to the OS executing inside clone
%% VMs. There are six main components.
Xenハイパーバイザに手を加えて、存在しないリソースへのアクセスがあったときのリカバーをスムーズに行えるようにしたもの。
dom0上で稼働するサポートプロセス群で、存在しないVMの状態を転送するもの。
クローンVM内で実行されるOSに対する修正。
簡単にまとめると、これらがSnowFlockを構成する。
主要なコンポーネントは次の六つだ。

\begin{aosaitemize}

  %% \item VM Descriptor: This small object is used to seed the clone,
  %% and holds the bare-bones skeleton of the VM as needed to begin
  %% execution.  It lacks the guts and muscle needed to perform any
  %% useful work.
  \item VM Descriptor：この小さなオブジェクトを使って
  クローンの種をまき、VMのベアボーンを保持して必要に応じて実行開始できるようにする。
  実際の作業をするために必要な馬力はない。

  %% \item Multicast Distribution System (\code{mcdist}): This
  %% parent-side system efficiently distributes the VM state
  %% information simultaneously to all clones.
  \item Multicast Distribution System (\code{mcdist})：
  これは親側のシステムで、VMの状態に関する情報をすべてのクローンに対して
  効率的に同時配信する。

  %% \item Memory Server Process: This parent-side process maintains a
  %% frozen copy of the parent's state, and makes it available to all
  %% clones on demand through \code{mcdist}.
  \item Memory Server Process：
  これは親側のプロセスで、親の状態のコピーを管理する。そして、すべてのクローンに対して
  必要に応じて\code{mcdist}経由で提供する。

  %% \item Memtap Process: This clone-side process acts on the clone's
  %% behalf, and communicates with the memory server to request pages
  %% that are needed but missing.
  \item Memtap Process：
  これはクライアント側のプロセスで、クライアントの代わりに働く。
  メモリーサーバーと通信をして、まだ存在しないが必要になったページについてのリクエストを出す。

  %% \item Clone Enlightenment: The guest kernel running inside the
  %% clones can alleviate the on-demand transfer of VM state by
  %% providing hints to the VMM\@. This is optional but highly desirable
  %% for efficiency.
  \item Clone Enlightenment：
  クローンの中で動くゲストカーネルは、オンデマンドでのVM状態の転送を緩和するために
  VMMにヒントを提供できる。これは必須ではないが、効率を考えるとかなりおすすめだ。

  %% \item Control Stack: Daemons run on each physical host to
  %% orchestrate the other components and manage the SnowFlock parent and clone VMs.
  \item Control Stack：
  各物理ホスト上で動くデーモンで、他のコンポーネントをとりまとめる役割を果たす。
  SnowFlockの親とクローンVMを管理する。

\end{aosaitemize}

%% \aosafigure{../images/snowflock/drawing.pdf}{SnowFlock VM Replication Architecture}{fig.snowflock.arch}
\aosafigure{../images/snowflock/drawing.eps}{SnowFlock VMレプリケーションのアーキテクチャ}{fig.snowflock.arch}

%% Pictorially speaking, \aosafigref{fig.snowflock.arch} depicts the
%% process of cloning a VM, showing the the four main steps: (1)
%% suspending the parent VM to produce an architectural descriptor; (2)
%% distributing this descriptor to all target hosts; (3) initiating
%% clones that are mostly empty state-wise; and (4) propagating state
%% on-demand. The figure also depicts the use of multicast distribution
%% with \code{mcdist}, and fetch avoidance via guest enlightenment.
図で説明しよう。\aosafigref{fig.snowflock.arch}はVMのクローン手順を表した図で、
四つの主要な手順を示している。(1) 親VMをサスペンドして構造ディスクリプタを作り、
(2) このディスクリプタをすべてのターゲットホストに配布し、
(3) ほぼ空っぽの状態のクローンを立ち上げ、
(4) オンデマンドで状態を伝搬させる。
この図は、\code{mcdist}によるマルチキャスト分散や
ゲストのClone Enlightenmentによるヒントの提供も示している。

%% If you're interested in trying SnowFlock, it's available in two
%% flavors.  The documentation and open source code for the original
%% University of Toronto SnowFlock research project are
%% available\footnote{\url{http://sysweb.cs.toronto.edu/projects/1}}
%% If you'd prefer to take
%% the industrial-strength version for a spin, a free, non-commercial
%% license is available from GridCentric 
%% Inc.\footnote{\url{http://www.gridcentriclabs.com/architecture-of-open-source-applications}}
%% Because SnowFlock includes changes to the hypervisor and requires
%% access to dom0, installing SnowFlock requires privileged access on the
%% host machines. For that reason, you'll need to use your own hardware,
%% and won't be able to try it out as a user in a commercial cloud
%% environment such as Amazon's EC2.
SnowFlockを試してみようと思ったら、選択肢は次の二種類だ。
まずは、ドキュメントつきのオープンソースのコード。これがオリジナルで、トロント大学のSnowFlock研究プロジェクト
\footnote{\url{http://sysweb.cs.toronto.edu/projects/1}}
で公開されている。ちょっと実運用で試してみたいのでそれに耐えるバージョンが欲しいという場合は、
フリーで非商用のライセンスのものがGridCentric  Inc.
\footnote{\url{http://www.gridcentriclabs.com/architecture-of-open-source-applications}}
から公開されている。
SnowFlockはハイパーバイザに手を入れているしdom0にアクセスする必要もあるので、
SnowFlockをインストールするにはホストマシンの特権アカウントが必要だ。
そのため、試すなら自分のハードウェアで使う必要があるだろう。
Amazon EC2などの商用クラウド環境で、ユーザーレベルで試すことはできない。

%% Throughout the next few sections we'll describe the different pieces
%% that cooperate to achieve instantaneous and efficient cloning. All
%% the pieces we will describe fit together as shown in
%% \aosafigref{fig.snowflock.components}.
この後のセクションでは、即座に効率的なクローンを実現するための各パーツについて説明する。
ここで説明するすべてのパーツが\aosafigref{fig.snowflock.components}で示すように組み合わさることになる。

%% \aosafigure{../images/snowflock/drawing-arch.eps}{Software Components of SnowFlock}{fig.snowflock.components}
\aosafigure{../images/snowflock/drawing-arch.eps}{SnowFlockのソフトウェアコンポーネント}{fig.snowflock.components}

\end{aosasect1}

%% \begin{aosasect1}{Architectural VM Descriptor}
\begin{aosasect1}{VM構造ディスクリプタ}

%% The key design decision for SnowFlock is to postpone the replication
%% of VM state to a lazy runtime operation. In other words, copying the
%% memory of a VM is a late binding operation, allowing for many
%% opportunities for optimization.
SnowFlockにおける設計上の重要な決断が、
VMの状態のコピーを先送りにして実行時に行うようにしたことだ。
言い換えると、VMのメモリのコピーを遅延束縛操作にして、
最適化できる余地を増やしたということである。

%% The first step to carry out this design decision is the generation of
%% an architectural descriptor of the VM state. This is the seed that
%% will be used to create clone VMs. It contains the bare minimum
%% necessary to create a VM and make it schedulable. As the name implies,
%% this bare minimum consists of data structures needed by the underlying
%% architectural specification.  In the case of SnowFlock, the
%% architecture is a combination of Intel x86 processor requirements and
%% Xen requirements. The architectural descriptor thus contains data
%% structures such as page tables, virtual registers, device metadata,
%% wallclock timestamps, etc. We refer the interested reader to~\cite{bib:snowflocktocs}
%% for an in-depth description of the contents of the
%% architectural descriptor.
この決断を実行するための第一歩が、VMの状態を表す構造ディスクリプタの生成だ。
これが、クローンVMを作るときに使う種となる。
ディスクリプタには、VMを作るために最低限必要な内容だけが含まれており、
VMの作成予定を立てて実行できるようになっている。
その名の通り、必要最低限な内容とは、基盤となる構造を作るために必要なデータである。
SnowFlockの場合の構造とは、Intel x86プロセッサとXenだ。
したがって、構造ディスクリプタの内容は、
ページテーブルや仮想レジスタ、デバイスのメタデータ、時計のタイムスタンプなどといったデータとなる。
構造ディスクリプタの内容に関する詳細な情報に関しては
~\cite{bib:snowflocktocs}を参考にした。

%% An architectural descriptor has three important properties: First, it
%% can be created in little time; 200 milliseconds is not
%% uncommon. Second, it is small, typically three orders of magnitude
%% smaller than the memory allocation of the originating VM (1 MB for a 1
%% GB VM). And third, a clone VM can be created from a descriptor in less
%% than a second (typically 800 milliseconds).
構造ディスクリプタには、三つの重要な特徴がある。
まず、短時間で作れること。200ミリ秒で作れるというのも珍しいことではない。
次に、小さいこと。一般的には、元のVMのメモリ割り当て量よりも桁が三つくらい少なくなる。
つまり、メモリ1GBのVMなら、1MB程度になる。
最後に、ディスクリプタからのクローンVMの作成が一秒未満で終わること。一般的には800ミリ秒程度になる。

%% The catch, of course, is that the cloned VMs are missing most of their
%% memory state by the time they are created from the descriptor. The
%% following sections explain how we solve this problem---and how we take
%% advantage of the opportunities for optimization it presents.
もちろん問題もあって、ディスクリプタからVMをクローンした直後の時点では、
メモリの状態がほとんど存在しない状態になる。その問題をいかにして解決するのか。
それをこの後のセクションで解説する。これはまた、最適化のチャンスをいかに活用するのか、
という説明でもある。

\end{aosasect1}

%% \begin{aosasect1}{Parent-Side Components}
\begin{aosasect1}{親側のコンポーネント}

%% Once a VM is cloned it becomes a parent for its children or
%% clones.  Like all responsible parents, it needs to look out for the
%% well-being of its descendants. It does so by setting up a set of
%% services that provision memory and disk state to cloned VMs on demand.
あるVMのクローンを作ると、元のVMはそのクローン(子ども)たちの親になる。
親っていうのは、自分の子どもたちの面倒を見なきゃいけないものだ。
そのため、いくつかのサービスを用意して、
子どもたちからメモリやディスク状態の配布要求があったときに応えられるようにする。

%% \begin{aosasect2}{Memserver Process}
\begin{aosasect2}{Memserverプロセス}

%% When the architectural descriptor is created, the VM is stopped in its
%% tracks throughout the process. This is so the VM memory state settles;
%% before actually pausing a VM and descheduling from execution,
%% internal OS drivers quiesce into a state from which clones can
%% reconnect to the external world in their new enclosing VMs. We take
%% advantage of this quiescent state to create a ``memory server'',
%% or \code{memserver}.
構造ディスクリプタを作る間は、VMがいったん停止する。
これは、VMの状態を安定させるためである。実際にVMを止めて
実行スケジュールから外す前に、内部OSドライバーが休止状態に入る。
クローン側では、新たなVMでこの状態から外界との接続を再開できる。
この休止状態を活用するために作ったのが「メモリサーバー」。またの名を\code{memserver}という。

%% The memory server will provide all clones with the bits of memory they
%% need from the parent. Memory is propagated at the granularity of an
%% x86 memory page (4 kbytes). In its simplest form, the memory server sits
%% waiting for page requests from clones, and serves one page at a time,
%% one clone at a time.
メモリサーバーは、すべてのクローンに対して必要に応じて親からメモリを与える役割を果たす。
その粒度は、x86のメモリページ(4kバイト)と同じ単位だ。
最も単純な形式だと、メモリサーバーはクローンからのリクエストを待ち受けて、
一つのクローンに対して一度に1ページずつメモリを与える。

%% However, this is the very same memory the parent VM needs to use to
%% keep executing. If we would allow the parent to just go ahead and
%% modify this memory, we would serve corrupted memory contents to clone
%% VMs: the memory served would be different from that at the point of
%% cloning, and clones would be mightily confused. In kernel hacking
%% terms, this is a sure recipe for stack traces.
しかし、ここで分け与えるメモリは、親VMの実行に必要なメモリとまったく同じものだ。
親側でのメモリの内容も変わり続けるので、もしそれをそのままクローンに与えてしまうと
壊れた状態のメモリを渡すことになるかもしれない。
クローン側で期待しているのはクローンを作った時点のメモリの状態なのに、
実際にやってきた内容はそれとは違う。クローンはきっと戸惑うだろう。
カーネルハックの世界だと、これはきっと「スタックトレースを出すための確実な方法」
ってことになる。

%% To circumvent this problem, a classical OS notion comes to the rescue:
%% Copy-on-Write, or CoW memory. By enlisting the aid of the Xen
%% hypervisor, we can remove writing privileges from all pages of memory
%% in the parent VM\@. When the parent actually tries to modify one page, a
%% hardware page fault is triggered.  Xen knows why this happened, and
%% makes a copy of the page. The parent VM is allowed to write to the original
%% page and continue execution, while the memory server is told to use
%% the copy, which is kept read-only. In this manner, the memory state at the point of cloning
%% remains frozen so that clones are not confused, while the parent is
%% able to proceed with execution. The overhead of CoW is minimal:
%% similar mechanisms are used by Linux, for example, when creating new
%% processes.
この問題を回避するための助けとなったのが、昔ながらのOSにある概念である
コピーオンライト(CoW)メモリだ。Xenハイパーバイザの助けを得れば、
親VMのメモリ内のすべてのページに対する書き込み権限を削除できる。
こうすれば、親がどこかのページを書き換えようとしたときに
ハードウェアページフォルトが発生するようになる。
Xenはなぜそうなったのかを知っているので、そのページのコピーを作る。
コピーが終われば、親VMは本来のページへの書き込みを認められて処理を続行できる。
一方メモリサーバーには、今後はコピーの方を使うように伝えてコピーのほうを読み込み専用にする。
この方式を使えば、クローンした時点でのメモリの状態が残ったままになるので
クローン側で混乱することがなくなる。その一方、親は親で処理を続けられるのだ。
CoWによるオーバーヘッドはわずかなものだ。
実際、たとえばLinuxで新たなプロセスを作るときにも同じ手順が使われている。

\end{aosasect2}

%% \begin{aosasect2}{Multicasting with Mcdist}
\begin{aosasect2}{Mcdistによるマルチキャスト}

%% Clones are typically afflicted with an existential syndrome known as
%% ``fate determinism.'' We expect clones to be created for a single
%% purpose: for example, to align X chains of DNA against a segment Y of
%% a database. Further, we expect a set of clones to be created so that
%% all siblings do the same, perhaps aligning the same X chains against
%% different segments of the database, or aligning different chains
%% against the same segment Y\@. Clones will thus clearly exhibit a great
%% amount of temporal locality in their memory accesses: they will use
%% the same code and large portions of common data.
クローンは一般的に、いわゆる「運命決定論」という症状に苦しめられている。
私たちは、クローンは何かひとつの目的のために作られるものだと考えている。
たとえば、X本のDNA鎖をデータベースのセグメントYに割り当てるといったものだ。
さらに、複数のクローンをつくったときには、それぞれのクローンが同じことをするものと考える。
たとえば同じ鎖Xをデータベースのさまざまなセグメントに割り当てたり、
それぞれ別々の鎖を同じセグメントYに割り当てたりといったものだ。
したがって、クローンたちのメモリアクセスは時間局所性が大きくなることは明白だ。
同じようなコードを使い、大部分は同じようなデータを扱うことになる。

%% We exploit the opportunities for temporal locality through \code{mcdist}, our
%% own multicast distribution system tailored to SnowFlock. Mcdist uses
%% IP multicast to simultaneously distribute the same packet to a set of
%% receivers. It takes advantage of network hardware parallelism to
%% decrease the load on the memory server. By sending a reply to all
%% clones on the first request for a page, each clone's requests act as a
%% prefetch for its siblings, because of their similar memory access
%% patterns.
そこで、その時間局所性を活用するために\code{mcdist}を使う。
これは、SnowFlockにあわせて自作したマルチキャスト配信システムである。
mcdistは、IPマルチキャストを使って同じパケットを複数の受信者に同時配信する。
ネットワークハードウェアの並列性を活用して、メモリサーバーへの負荷を軽減する。
あるページへの最初のリクエストに対しての応答を全クローンに向けて行うことで、
各クローンからのリクエストがその兄弟たちへのプリフェッチとして機能するようになる。
兄弟たちのメモリアクセスパターンは似たようなものだからである。

%% Unlike other multicast systems, \code{mcdist} does not have to be reliable,
%% does not have to deliver packets in an ordered manner, and does not
%% have to atomically deliver a reply to all intended
%% receivers. Multicast is strictly an optimization, and delivery need
%% only be ensured to the clone explicitly requesting a page. The design
%% is thus elegantly simple: the server simply multicasts responses,
%% while clients time-out if they have not received a reply for a
%% request, and retry the request.
他のマルチキャストシステムとは違い、
\code{mcdist}には信頼性は要求されないし
順序どおりにパケットを配送する必要もない。
また、すべての受信者に対してアトミックに応答を返す必要もない。
ここでのマルチキャストは厳密に言えば最適化であり、
確実に配送しないといけないのは明示的にページを要求したクローンに対してだけだ。
そのため、すっきりとシンプルな設計にした。
サーバー側は単に応答をマルチキャストするだけ。
クライアント側は、もしリクエストに対する応答がなければタイムアウトして、
リクエストを再送する。

%% Three optimizations specific to SnowFlock are included in \code{mcdist}:
SnowFlockのための最適化として、次の三つが\code{mcdist}に仕込まれている。

\begin{aosaitemize}

  %% \item Lockstep Detection: When temporal locality does happen,
  %% multiple clones request the same page in very close
  %% succession. The \code{mcdist} server ignores all but the first of such
  %% requests.
  \item 連続リクエストの検出：
  時間局所性が発生すると、複数のクローンがほぼ同時に同じページをリクエストすることになる。
  \code{mcdist}サーバーは、そんな場合に最初のリクエストだけを受け付けてその他を無視する。

  %% \item Flow Control: Receivers piggyback their receive rate on
  %% requests.  The server throttles its sending rate to a weighted
  %% average of the clients' receive rate. Otherwise, receivers will be
  %% drowned by too many pages sent by an eager server.
  \item フロー制御：
  受信者は、リクエストと同時に受信レートを送る。
  サーバー側では、送信レートを調整してクライアントの受信レートに対する重み付けをする。
  そうしないと、サーバーから大量のページが送られてきてクライアントが処理しきれなくなるだろう。

  %% \item End Game: When the server has sent most pages, it falls back
  %%   to unicast responses. Most requests at this point are retries, and
  %%   thus blasting a page through the wire to all clones is
  %%   unnecessary.
  \item 試合終了：
  サーバーが大半のページを配信し終えたら、ユニキャスト方式に移行する。
  この時点ではリクエストの大半が再送要求になるので、
  全クローンに対してページを送りつけなくてもいいからである。

\end{aosaitemize}

\end{aosasect2}

%% \begin{aosasect2}{Virtual Disk}
\begin{aosasect2}{仮想ディスク}

%% SnowFlock clones, due to their short life span and fate determinism,
%% rarely use their disk. The virtual disk for a SnowFlock VM houses the
%% root partition with binaries, libraries and configuration files. Heavy
%% data processing is done through suitable filesystems such as HDFS
%% (\aosachapref{s:hdfs}) or PVFS\@. Thus, when SnowFlock clones decide
%% to read from their root disk, they typically have their requests
%% satisfied by the kernel filesystem page cache.
SnowFlockのクローンは、
(生存期間が短めであることや、生存決定論のせいもあって)
めったにディスクを使うことがない。
SnowFlock VMの仮想ディスクはルートパーティションを保持し、
バイナリやライブラリそして設定ファイルを扱う。重たいデータ処理などは、
HDFS (\aosachapref{s:hdfs})やPVFSなどのそれに適したファイルシステムを使って行う。
したがって、SnowFlockのクローンがルートディスクから読み込もうとしたときには、
カーネルのファイルシステムのページキャッシュを満たすリクエストをすることになる。

%% Having said that, we still need to provide access to the virtual disk
%% for clones, in the rare instance that such access is needed. We
%% adopted the path of least resistance here, and implemented the disk by
%% closely following the memory replication design. First, the state of
%% the disk is frozen at the time of cloning. The parent VM keeps using
%% its disk in a CoW manner: writes are sent to a separate location in
%% backing storage, while the view of the disk clones expect remains
%% immutable.  Second, disk state is multicast to all clones, using
%% \code{mcdist}, with the same 4 KB page granularity, and under the same
%% expectations of temporal locality. Third, replicated disk state for a
%% clone VM is strictly transient: it is stored in a sparse flat file
%% which is deleted once the clone is destroyed.
それでもなお、クローンから仮想ディスクへのアクセスはできるようにしておく必要がある。
ごくまれにでも、そんなアクセスが必要となる場合があるからである。
私たちが選んだのは一番抵抗の少ない方法で、
ディスクの実装をメモリのレプリケーション設定にできるだけ近づけるようにした。
まず、クローンするときにはディスクの状態をいったん固める。
つまり、親VMでディスクを使うときにはCoW方式で行う。
ディスクへの書き込みは別の場所に保存されるということだ。
というのも、クローン側からはクローンした時点でのディスクの状態が見えてほしいからである。
次に、ディスクの状態は\code{mcdist}を使って全クローンにマルチキャストする。
メモリと同様に4 KB単位の粒度で、時間局所性に関しても同じように考える。
最後に、クローンVMに複製されたディスクの状態は永続させない。
ディスクの状態はまばらなフラットファイルに格納され、クローンが破棄されるとともに削除される。

\end{aosasect2}

\end{aosasect1}

%% \begin{aosasect1}{Clone-Side Components}
\begin{aosasect1}{クローン側のコンポーネント}

%% Clones are hollow shells when they are created from an architectural
%% descriptor, so like everybody else, they need a lot of help from their
%% parents to grow up: the children VMs move out and immediately call
%% home whenever they notice something they need is missing, asking their
%% parent to send it over right away.
クローンは、構造ディスクリプタから作成した時点では中身がない空っぽの状態だ。
というわけで、成長するには親の助けが必要だ。家を飛び出していった子どもたちは、
必要なものが手元にないことに気付いた時点で実家に連絡して、
「すぐに送って！」と親にお願いする。

%% \begin{aosasect2}{Memtap Process}
\begin{aosasect2}{Memtapプロセス}

%% Attached to each clone after creation, the \code{memtap} process is the
%% lifeline of a clone. It maps all of the memory of the clone and fills
%% it on demand as needed.  It enlists some crucial bits of help from the
%% Xen hypervisor: access permission to the memory pages of the clones is
%% turned off, and hardware faults caused by first access to a page are
%% routed by the hypervisor into the \code{memtap} process.
クローンができあがるたびにそれにアタッチされるのが\code{memtap}プロセスで、
これがクローンの命綱となる。クローンのメモリ全体をマップして、
必要に応じてその中身を埋める役割を果たす。
このプロセスは、Xenハイパーバイザからの助けを得て動く。
クローンのメモリページへのアクセス権を無効にして、
あるページへの最初のアクセスがハードウェアフォルトを起こした時点で
ハイパーバイザが\code{memtap}プロセスに処理を回す。

%% In its simplest incarnation, the \code{memtap} process simply asks the
%% memory server for the faulting page, but there are more complicated
%% scenarios as well.  First, \code{memtap} helpers use \code{mcdist}. This means that at any
%% point in time, any page could arrive by virtue of having been
%% requested by another clone---the beauty of asynchronous
%% prefetching. Second, we allow SnowFlock VMs to be multi-processor VMs.
%% There wouldn't be much fun otherwise. This means that multiple faults
%% need to be handled in parallel, perhaps even for the same page.
%% Third, in later versions \code{memtap} helpers can explicitly prefetch a
%% batch of pages, which can arrive in any order given the lack of
%% guarantees from the \code{mcdist} server.  Any of these factors could have led
%% to a concurrency nightmare, and we have all of them.
単純に言ってしまえば、\code{memtap}プロセスの役割は
フォルトが発生したページの配送をメモリサーバーに依頼するだけのことだ。
しかしそれ以外にも、もっと複雑なシナリオもある。
まず、\code{memtap}ヘルパーは\code{mcdist}を利用する。
つまり、他のクローンが要求したページが任意の時点で到着することがある。
そう、非同期プリフェッチってやつだ。
次に、SnowFlock VMをマルチプロセッサVMにすることができる。
そうしなければ、いろんな楽しいこともできなかっただろう。
これはつまり、複数のフォルトを並列に扱う必要があるということだ。
場合によっては同じページが含まれるかもしれない。
最後に、最近のバージョンの\code{memtap}ヘルパーには、
ページ群を明示的にプリフェッチする機能がある。
ただし、ページを取得する順序がどうなるかはわからない。
\code{mcdist}サーバーにそれを保証する機能がないからだ。
これらの要素はすべて同時並行性に関する悪夢を引き起こす元であり、
実際に私たちもそれを経験した。

%% The entire \code{memtap} design centers on a page presence bitmap. The bitmap
%% is created and initialized when the architectural descriptor is
%% processed to create the clone VM\@.
%% The bitmap is a flat bit array sized by the number of pages the VM's memory can hold. 
%% Intel processors have handy atomic
%% bit mutation instructions: setting a bit, or doing a test and set, can
%% happen with the guarantee of atomicity with respect to other
%% processors in the same box.  This allows us to avoid
%% locks in most cases, and thus to provide access to the bitmap by
%% different entities in different protection domains: the Xen
%% hypervisor, the \code{memtap} process, and the cloned guest kernel itself.
\code{memtap}の全体的な設計の中心となるのが、ページの存在を表すビットマップだ。
このビットマップを作って初期化するのは、構造ディスクリプタがクローンVMを作るときである。
このビットマップは一次元のビット配列で、VMのメモリが保持できるページ数と同じだけのサイズになる。
Intelプロセッサには、便利なアトミックビット操作インストラクションが用意されている。
ビットを立てたり、状態を調べてから設定したりといった操作が、
同じマシン内の他のプロセッサに対してアトミックに行えることが保証されるのだ。
そのおかげで、大半の場合にロックを回避でき、
別の保護ドメインにある別のエンティティ
(Xenハイパーバイザや\code{memtap}プロセス、そしてクローンしたゲストのカーネル自身など)
からのビットマップへのアクセスもできるようになる。

%% When Xen handles a hardware page fault due to a first access to a
%% page, it uses the bitmap to decide whether it needs to alert
%% \code{memtap}. It also uses the bitmap to enqueue multiple faulting virtual
%% processors as dependent on the same absent page. Memtap buffers pages
%% as they arrive.  When its buffer is full or an explicitly requested
%% page arrives, the VM is paused, and the bitmap is used to discard any
%% duplicate pages that have arrived but are already present. Any
%% remaining pages that are needed are then copied into the VM memory,
%% and the appropriate bitmap bits are set.
あるページへの最初のアクセスで発生したハードウェアページフォルトをXenが処理するときに、
このビットマップを使って\code{memtap}に通知するかどうかを判断する。
また、同じくこのビットマップを使って、
複数の仮想プロセッサが同じページでフォルトを起こしている場合にキューに入れたりする。
Memtapは、到着したページをバッファに格納する。
バッファがいっぱいになったり明示的にリクエストしたページが届いたりしたときは
VMを一時停止させ、ビットマップを使って不要なページを破棄する。
不要なページとは、重複して届いたけれど既に存在するようなページのことだ。
残りのページは必要なものなのでVMのメモリ内にコピーし、
それに合わせてビットマップ上の適切なビットを立てる。

\end{aosasect2}

%% \begin{aosasect2}{Clever Clones Avoid Unnecessary Fetches}
\begin{aosasect2}{無駄なフェッチを回避する賢いクローン}

%% We just mentioned that the page presence bitmap is visible to the
%% kernel running inside the clone, and that no locks are needed to
%% modify it. This gives clones a powerful ``enlightenment'' tool: they can prevent the
%% fetching of pages by modifying the bitmap and pretending they are
%% present. This is extremely useful performance-wise, and safe to do
%% when pages will be completely overwritten before they are used.
先ほど言ったとおり、ページビットマップはクローン内で稼働中のカーネルからも見えており、
ビットマップを変更するときにロックは不要だ。これは、クローンにとって非常に強力な
``enlightenment''ツールとなる。ビットマップをいじって特定のページが存在するように見せかければ、
そのページをフェッチさせないようにできるのだ。
これはパフォーマンス的に極めて有用で、
ページを使う前に完全に上書きしてしまうようなときにも安全に行える。

%% There happens to be a very common situation when this happens and
%% fetches can be avoided. All memory allocations in the kernel (using
%% \code{vmalloc}, \code{kzalloc}, \code{get\_free\_page},
%% user-space \code{brk}, and the like) are ultimately
%% handled by the kernel page allocator. Typically pages are requested by
%% intermediate allocators which manage finer-grained chunks: the slab
%% allocator, the glibc malloc allocator for a user-space process,
%% etc. However, whether allocation is explicit or implicit,
%% one key semantic implication
%% always holds true: no one cares about what the page contained,
%% because its contents will be arbitrarily overwritten. Why
%% fetch such a page, then? There is no reason to do so, and empirical
%% experience shows that avoiding such fetches is tremendously
%% advantageous.
このような状況になってフェッチを回避するようなことは非常によくある話だ。
カーネル内でのすべてのメモリ確保(\code{vmalloc}や\code{kzalloc}、\code{get\_free\_page}、ユーザー空間での\code{brk}など)
は、結局のところカーネルのページアロケータが処理する。
一般的に、ページをリクエストするのは中間アロケータで、ここではよりきめ細やかな塊を管理する。
slabアロケータ、そしてユーザー空間プロセス用のglibc mallocアロケータなどである。
しかし、明示的なアロケーションであっても暗黙のアロケーションであっても、これだけは常に正しい。
そのページに何が含まれるかなんて、誰も気にしない。ページの内容なんてどうにでも上書きできるからだ。
じゃあなぜそんなページをフェッチするんだって？
理由なんかない。経験上、そんなページのフェッチは回避するのが大いに有用なのだ。

\end{aosasect2}

\end{aosasect1}

%% \begin{aosasect1}{VM Cloning Application Interface}
\begin{aosasect1}{VMクローニングアプリケーションのインターフェイス}

%% So far we have focused on the internals of cloning a VM
%% efficiently. As much fun as solipsistic systems can be, we need to
%% turn our attention to those who will use the system: applications.
ここまでは、VMを効率的にクローンするための内部構造に焦点を合わせてきた。
自分たちの世界にだけ浸っているわけにもいかないので、
ここらでシステムを使う側にも目を向けよう。アプリケーション側の視点で話を進める。

%% \begin{aosasect2}{API Implementation}
\begin{aosasect2}{APIの実装}

%% VM Cloning is offered to the application via the simple SnowFlock API,
%% depicted in \aosafigref{fig.snowflock.cloningapi}. Cloning is
%% basically a two-stage process. You first request an allocation for the
%% clone instances, although due to the system policies that are in effect, that
%% allocation may be smaller than requested.  Second, you use the
%% allocation to clone your VM\@.  A key assumption is that your VM focuses
%% on a single operation.  VM Cloning is appropriate for
%% single-application VMs such as a web server or a render farm
%% component.  If you have a hundred-process desktop environment in which
%% multiple applications concurrently call VM cloning, you're headed for
%% chaos.
VMクローニングをアプリケーションから行うには、シンプルなSnowFlock APIを使う。
\aosafigref{fig.snowflock.cloningapi}に示すようなものだ。
クローニングは基本的には二段階のプロセスである。
まず最初に、クローンインスタンス用の割り当てを要求する。
しかし、システムのポリシーが原因で、要求したよりも少なめの割り当てしかもらえないこともあり得る。
次に、割り当て分を使ってVMをクローンする。
ここでポイントとなるのが、VMは単一の操作に注力するものだという前提である。
VMのクローニングが適しているのは、単一用途のVMの場合である。
ウェブサーバーやレンダリングファームなどがその一例だ。
100プロセスのデスクトップ環境で複数のアプリケーションが同時に
VMのクローニングをしたりなどすれば、大混乱になってしまう。

\begin{table}\centering
  \begin{tabular}{ |l p{7cm}| }
    \hline
    \code{sf\_request\_ticket(n)}
    &
    %% Requests an allocation for \code{n} clones.  Returns a
    %% \code{ticket} describing an allocation for \code{m$\leq$n}
    %% clones.
    \code{n}個のクローン用に割り当てを要求する。
    \code{m$\leq$n}個のクローン用の割り当てを示す\code{ticket}を返す。
    \\

    \code{sf\_clone(ticket)}
    &
    %% Clones, using the \code{ticket} allocation. Returns the clone
    %% \code{ID}, \code{0$\leq$ID{\textless}m}.
    \code{ticket}の割り当てにしたがってクローンを作る。
    クローンの\code{ID}(\code{0$\leq$ID{\textless}m})を返す。
    \\

    \code{sf\_checkpoint\_parent()}
    &
    %% Prepares an immutable checkpoint \code{C} of the parent VM to be
    %% used for creating clones at an arbitrarily later time.
    親VMの、イミュータブルなチェックポイント\code{C}を作る。
    これを使えば、その後いつでもクローンを作れるようになる。
    \\

    \code{sf\_create\_clones(C, ticket)}
    &
    %% Same as \code{sf\_clone}, uses the checkpoint \code{C}.
    %% Clones will begin execution at the point at which
    %% the corresponding \code{sf\_checkpoint\_parent()} was invoked.
    \code{sf\_clone}と同じだが、チェックポイント\code{C}を利用する。
    対応する\code{sf\_checkpoint\_parent()}を実行した時点の状態から
    クローンの実行が始まる。
    \\

    \code{sf\_exit()}
    &
    %% For children \code{(1$\leq$ID{\textless}m)}, terminates
    %% the child.
    子VM\code{(1$\leq$ID{\textless}m)}を終了する。
    \\

    \code{sf\_join(ticket)}
    &
    %% For the parent \code{(ID = 0)}, blocks until all children in the
    %% \code{ticket} reach their \code{sf\_exit} call.  At that point all
    %% children are terminated and the \code{ticket} is discarded.
    \code{ticket}内のすべての子が\code{sf\_exit}を呼ぶまで、親\code{(ID = 0)}
    をブロックする。この時点ですべての子が終了し、\code{ticket}が破棄される。
    \\

    \code{sf\_kill(ticket)}
    &
    %% Parent only, discards \code{ticket} and immediately kills all
    %% associated children.
    親限定で、\code{ticket}を破棄して関連するすべての子を終了させる。
    \\
    \hline
  \end{tabular}
  %% \caption{The SnowFlock VM Cloning API}
  \caption{SnowFlock VMクローニングAPI}
  \label{fig.snowflock.cloningapi}
\end{table}

%% The API simply marshals messages and posts them to the XenStore, a
%% shared-memory low-throughput interface used by Xen for control plane
%% transactions. A SnowFlock Local Daemon (SFLD) executes on the
%% hypervisor and listens for such requests. Messages are unmarshalled,
%% executed, and requests posted back.
このAPIは、単にメッセージをマーシャルしてXenStoreにポストするだけである。
XenStoreとは共有メモリの低スループットインターフェイスで、Xenがプレーンなトランザクションを制御するために使っている。
SnowFlock Local Daemon (SFLD)がハイパーバイザ上で稼働し、このリクエストを待ち受ける。
受けとったメッセージをアンマーシャルして実行し、リクエストを戻す。

%% Programs can control VM Cloning directly through the API, which is
%% available for C, C++, Python and Java. Shell scripts that harness the
%% execution of a program can use the provided command-line scripts
%% instead.  Parallel frameworks such as MPI can embed the API: MPI
%% programs can then use SnowFlock without even knowing, and with no
%% modification to their source.
%% Load balancers sitting in front of web or application
%% servers can use the API to clone the servers they manage.
プログラムからVMクローニングを直接制御するときにはAPIを利用する。
用意されているのはCやC++、Python、そしてJava用のAPIだ。
シェルスクリプトからプログラムを実行できない場合は、
代わりに使えるコマンドラインスクリプトが提供されている。
MPIのような並列プログラミングフレームワークにAPIを組み込むこともできる。
そうすれば、MPIのプログラムからSnowFlockを使えるようになり、
ソースへの変更も不要となる。
ウェブサーバーあるいはアプリケーションサーバーの前に置いた
ロードバランサーも、このAPIを使えば自身の管理するサーバーをクローンできる。

%% SFLDs orchestrate the execution of VM Cloning requests. They create
%% and transmit architectural descriptors, create cloned VMs, launch disk
%% and memory servers, and launch \code{memtap} helper processes.  They are a
%% miniature distributed system in charge of managing the VMs in a
%% physical cluster.
SFLDは、VMクローニングリクエストの実行の調整役となる。
SFLDが構造ディスクリプタを作ってそれを送信し、クローンVMを作成し、
ディスクとメモリサーバーを立ち上げ、
ヘルパープロセス\code{memtap}を立ち上げる。
これらはちょっとした分散システムであり、
物理クラスタ内のVMを管理する役割を果たす。

%% SFLDs defer allocation decisions to a central SnowFlock Master Daemon
%% (SFMD).  SFMD simply interfaces with appropriate cluster management
%% software. We did not see any need to reinvent the wheel here, and
%% deferred decisions on resource allocation, quotas, policies, etc.\  to
%% suitable software such as Sun Grid Engine or Platform EGO.
SFLDは、割り当ての判断を中央のSnowFlock Master Daemon (SFMD)に任せる。
SFMDは単に、適切なクラスタ管理ソフトウェアとのインターフェイスになるだけのものである。
こんなところで車輪の再発明をする必要もないので、リソース割り当てや領域の分配そしてポリシーなどは
Sun Grid EngineやPlatform EGOといった適切なソフトウェアに任せることにしたのだ。

\end{aosasect2}

%% \begin{aosasect2}{Necessary Mutations}
\begin{aosasect2}{欠かせない変異}

%% After cloning, most of the cloned VM's processes have no idea that
%% they are no longer the parent, and that they are now running in a
%% copy. In most aspects, this just works fine and causes no
%% issues. After all, the primary task of the OS is to isolate
%% applications from low-level details, such as the network identity.
%% Nonetheless, making the transition smooth requires a set of mechanisms
%% to be put in place. The meat of the problem is in managing the clone's
%% network identity; to avoid conflicts and confusion, we must introduce
%% slight mutations during the cloning process.  Also, because these
%% tweaks may necessitate higher-level accommodations, a hook is inserted
%% to allow the user to configure any necessary tasks, such as
%% (re)mounting network filesystems that rely on the clone's identity.
クローニングで作ったクローンVMのプロセスの大半は、
自分がもはや親ではなく親のコピーであるということを知るすべがない。
たいていの場合はそれでもうまく動くし問題はない。
結局のところ、OSの最大の目的はアプリケーションをローレベルのあれこれ
(ネットワーク上でのIDなど)から切り離すことである。
しかし、移行をスムーズに進めるにはいくつかの仕組みが必要となる。
問題の本質は、ネットワーク上でのクローンの一意性を管理することだ。
衝突や混乱を回避するために、クローン処理の中でちょっとした変異が必要となる。
また、これらの手入れで上位レベルでの調整を余儀なくされることもあるので、
フックを導入して必要なタスクをユーザーが設定できるようにする。
たとえば、クローンのネットワーク情報に基づいてマウントしているネットワークファイルシステムの
再マウントなどといったタスクである。

%% Clones are born to a world that is mostly not expecting them. The
%% parent VM is part of a network managed most likely by a DHCP server,
%% or by any other of the myriad ways sysadmins find to do their
%% job. Rather than assume a necessarily inflexible scenario, we place
%% the parent and all clones in their own private virtual network. Clones
%% from the same parent are all assigned a unique ID, and their IP
%% address in this private network is automatically set up upon cloning
%% as a function of the ID\@. This guarantees that no intervention from a
%% sysadmin is necessary, and that no IP address collisions will ever
%% happen.
クローンは、もともとその存在が予期されていなかった世界に生まれてきたものだ。
親VMは、もともと管理されたネットワークの一員であった。
たいていはDHCPサーバーの配下にあっただろう。
あるいはそれ以外の何かかもしれない。システム管理者が飯を食う種などいくらでもある。
必ずしも柔軟性のないシナリオを想定するのではなく、
私たちは親とすべてのクローンたちを同じプライベート仮想ネットワーク内に置くことにした。
同じ親からのクローンたちにはすべて一意なIDを割り当て、プライベートネットワーク内での
IPアドレスは、クローンの際にIDをもとに自動的に設定する。
これでシステム管理者の介入は一切不要となり、IPアドレスの衝突も発生しなくなる。

%% IP reconfiguration is performed directly by a hook we place on the
%% virtual network driver. However, we also rig the driver to
%% automatically generate synthetic DHCP responses. Thus, regardless of
%% your choice of distribution, your virtual network interface will
%% ensure that the proper IP coordinates are propagated to the guest OS,
%% even when you are restarting from scratch.
IPアドレスの再設定は、仮想ネットワークドライバ上に仕込んだフックが直接行う。
しかし、それとは別に、DHCPのレスポンスを自動生成するドライバも用意している。
したがって、どんなディストリビューションを選んだとしても、
仮想ネットワークインターフェイスはゲストOSに対して適切なIPアドレスを割り振ることが保証される。
スクラッチから再起動しても同様である。

%% To prevent clones from different parents colliding with each others'
%% virtual private networks---and to prevent mutual DDoS attacks---clone
%% virtual network are isolated at the Ethernet (or layer 2) level. We
%% hijack a range of Ethernet MAC OUIs~\footnote{OUI, or Organizational Unique ID,
%% is a range of MAC addresses assigned to a vendor.} and dedicate them to clones. The
%% OUI will be a function of the parent VM\@. Much like the ID of a VM
%% determines its IP address, it also determines its non-OUI Ethernet MAC
%% address.  The virtual network driver translates the MAC address the VM
%% believes it has to the one assigned as a function of its ID, and
%% filters out all traffic to and from virtual private network with
%% different OUIs. This isolation is equivalent to that achievable via
%% \code{ebtables}, although much simpler to implement.
別々の親からのクローンがお互いに相手の仮想プライベートネットワークと衝突してしまうことを防ぐため
---そしてお互いのDDoS攻撃を防ぐため---に、クローンの仮想ネットワークはイーサネットレベル
(レイヤー2)で隔離されている。
Ethernet MAC OUI~\footnote{Organizational Unique IDとは、ベンダーに割り当てられたMACアドレス範囲のことだ。}
を乗っ取り、そこをクローン専用にしているのだ。
このOUIは親VMの役割となる。
VMのIDをもとにしてそのIPアドレスを決めるのと同様に、OUI部分以外のMACアドレスもIDにもとづいて決める。
仮想ネットワークドライバは、VMが自分自身のIDにもとづいて与えられたと信じているMACアドレスを翻訳し、
仮想プライベートネットワークと外部との間のトラフィックをフィルタして別のOUIにする。
これは\code{ebtables}が使っているのと同じ方式だが、実装はそれよりもはるかにシンプルだ。

%% Having clones talk only to each other may be fun, but not fun enough.
%% Sometimes we will want our clones to reply to HTTP requests from the
%% Internet, or mount public data repositories. We equip any set of
%% parent and clones with a dedicated router VM\@. This tiny VM performs
%% firewalling, throttling and NATing of traffic from the clones to the
%% Internet. It also limits inbound connections to the parent VM and
%% well-known ports.  The router VM is lightweight but represents a
%% single point of centralization for network traffic, which can
%% seriously limit scalability. The same network rules could be applied
%% in a distributed fashion to each host upon which a clone VM runs. We
%% have not released that experimental patch.
クローンはクローン同士でしか通信できないようにするというのもおもしろいが、それでは不十分だ。
時にはクローンからインターネットにHTTPレスポンスを返したいこともあるだろうし、
公開されているデータリポジトリをマウントしたいこともあるだろう。
親やクローンの中からいくつかを選んで、専用のルーターVMにすることもできる。
この小さなVMの役割は、クローンたちとインターネットとの間のトラフィックの
ファイアウォールであったり流量制限であったりNATであったりする。
また、外部からの通信は親VMのwel-knownポートだけに限定している。
ルーターVMは軽量だが、ネットワークトラフィックを一元管理する単一点となる。
そのため、スケーラビリティに大きな制限ができてしまう。
同じようなネットワークルールを分散形式で適用し、クローンVMが稼働する各ホスト上に置くこともできるだろう。
そんな実験的なパッチは、まだリリースしていない。

%% SFLDs assign IDs, and teach the virtual network drivers how they
%% should configure themselves: internal MAC and IP addresses, DHCP
%% directives, router VM coordinates, filtering rules, etc.
SFLDはIDを割り当て、どんな設定にすべきかを仮想ネットワークドライバに伝える。
内部的なMACアドレスおよびIPアドレス、DHCPのディレクティブ、ルーターVMの設定、フィルタリング規則などである。

\end{aosasect2}

\end{aosasect1}

%% \begin{aosasect1}{Conclusion}
\begin{aosasect1}{結論}

%% By tweaking the Xen hypervisor and lazily transferring the VM's state,
%% SnowFlock can produce dozens of clones of a running VM in a few
%% seconds. Cloning VMs with SnowFlock is thus instantaneous and
%% live---it improves cloud usability by automating cluster management
%% and giving applications greater programmatic control over the cloud
%% resources. SnowFlock also improves cloud agility by speeding up VM
%% instantiation by a factor of 20, and by improving the performance of
%% most newly created VMs by leveraging their parent's warm, in-memory OS
%% and application caches. The keys to SnowFlock's efficient performance
%% are heuristics that avoid unnecessary page fetches, and the multicast
%% system that lets clone siblings cooperatively prefetch their
%% state. All it took was the clever application of a few tried-and-true
%% techniques, some sleight of hand, and a generous helping of
%% industrial-strength debugging.
Xenハイパーバイザに手を入れてVMの状態の転送を遅らせるようにしたことで、
SnowFlockは稼働中のVMのクローンを何十個も作れるようになった。
それもたった数秒でだ。つまり、SnowFlockにおけるVMのクローニングとは、
瞬時にその場で行えるものだということになる。
これはクラウドの使い勝手を大きく向上させた。
クラスタ管理は自動化できるし、
アプリケーションのプログラムからクラウドのリソースを操作することもできるようになった。
SnowFlockはまた、クラウドのアジリティも向上させた。
VMの立ち上げ速度は20倍高速化したし、
新しく作ったVMのパフォーマンスも向上した。親の環境の
まさに稼働中の状態(メモリやアプリケーションのキャッシュなど)
をそのまま引き継げたからである。
SnowFlockがパフォーマンスを向上させた鍵は、
ヒューリスティックを活用して無駄なページフェッチを回避したことと、
同じ親を持つクローン同士がマルチキャストシステムで状態をプリフェッチできるようにしたことだ。
これらすべての要因となったのが、
いくつかの実証済みのテクニックをうまく適用したことやそこに加えたちょっとした小技、そして業務レベルでのデバッグだ。

%% We learned two important lessons throughout the SnowFlock experience.
%% The first is the often-underestimated value of the KISS theorem. We
%% were expecting to implement complicated prefetching techniques to
%% alleviate the spate of requests for memory pages a clone would issue
%% upon startup.  This was, perhaps surprisingly, not necessary. The
%% system performs very well for many workloads based on one single
%% principle: bring the memory over as needed.  Another example of the
%% value of simplicity is the page presence bitmap. A simple data
%% structure with clear atomic access semantics greatly simplifies what
%% could have been a gruesome concurrency problem, with multiple virtual
%% CPUs competing for page updates with the asynchronous arrival of pages
%% via multicast.
SnowFlockを通じて得た大切な教訓が二つある。
第一の教訓は、過小評価されることが多いKISS原則である。
クローンの起動時に発生する大量のページ要求に対応するため、
当初は込み入ったプリフェッチ技術を実装しようとしていた。
以外にも、そんなことはしなくてもよかったのだ。
たったひとつの原則「必要になった時点でメモリを持ってくる」
に従うだけで、システムのパフォーマンスは高負荷時でも非常に良好だった。
シンプルに保つメリットを示すもうひとつの例が、ページの存在を表すビットマップだ。
データ構造をシンプルにしておき、きっちりとアトミックなアクセス方式を使うことで、
同時並行性に関するおぞましい問題をかなりシンプルにできた。
また、複数の仮想CPUが同じページの更新を要求する問題も、
マルチキャストを使ってページを非同期配信することで解決できた。

%% The second lesson is that scale does not lie. In other words, be
%% prepared to have your system shattered and new bottlenecks uncovered
%% every time you bump your scale by a power of two. This is intimately
%% tied with the previous lesson: simple and elegant solutions scale well
%% and do not hide unwelcome surprises as load increases. A prime example
%% of this principle is our \code{mcdist} system. In large-scale tests, a
%% TCP/IP-based page distribution mechanism fails miserably for hundreds
%% of clones. Mcdist succeeds by virtue of its extremely constrained and
%% well-defined roles: clients only care about their own pages; the
%% server only cares about maintaining a global flow control. By keeping
%% \code{mcdist} humble and simple, SnowFlock is able to scale extremely well.
第二の教訓は、規模は嘘をつかないということ。
言い換えれば、システムの規模が倍になるたびに
新たなボトルネックが発覚してシステムが大変なことになってしまうので
その準備が必要だということだ。
これは、先ほどの教訓と密接に関連する。
シンプルでエレガントなソリューションは規模が拡大してもうまく機能するし、
負荷が高まってもいやなことにならずに済ませられる。
この法則の主要な例が、\code{mcdist}システムだ。
大規模環境でのテストにおいて、TCP/IPベースのページ配信機構は
クローン数百台程度でぶざまに失敗してしまう。
mcdistは、窮屈なうまく定義したロールのおかげで成功をおさめた。
クライアントは自分のページだけを気にすればよくて、
サーバーは全体的なフロー制御だけを管理すればよいというものだ。
\code{mcdist}を控え目でシンプルなものに保つことで、
SnowFlockはとてもうまい具合にスケールできるようになった。

%% If you are interested in knowing more, you can visit the University of
%% Toronto site\footnote{\url{http://sysweb.cs.toronto.edu/projects/1}} for the
%% academic papers and open-source code licensed under GPLv2, and
%% GridCentric\footnote{\url{http://www.gridcentriclabs.com/}} for an industrial strength
%% implementation.
より詳しく知りたくなった人は、トロント大学のサイト
\footnote{\url{http://sysweb.cs.toronto.edu/projects/1}}
に行ってみよう。学術論文や、GPLv2でライセンスされたオープンソースのコードがある。
またGridCentric\footnote{\url{http://www.gridcentriclabs.com/}}
には、業務レベルでの使用に耐える実装がある。

\end{aosasect1}

\end{aosachapter}

